package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

var preorder = []int{3, 9, 20, 15, 7}
var inorder = []int{9, 3, 15, 20, 7}
var postorder = []int{9, 15, 7, 20, 3}

//前序和中序构造二叉树
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 {
		return nil
	}
	index := find(preorder, inorder) //找到分界点
	return &TreeNode{
		Val:   preorder[0],
		Left:  buildTree(preorder[1:len(inorder[:index])+1], inorder[:index]),
		Right: buildTree(preorder[len(inorder[:index])+1:], inorder[index+1:]),
	}
}

//前序和后序构造二叉树
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	if len(preorder) == 1 {
		return &TreeNode{Val: preorder[0], Left: nil, Right: nil}
	}
	index := find1(preorder, postorder) + 1 //找到分界点，即左子树长度
	return &TreeNode{
		Val:   preorder[0],
		Left:  constructFromPrePost(preorder[1:len(preorder[:index])+1], postorder[:index]),
		Right: constructFromPrePost(preorder[len(preorder[:index])+1:], postorder[index:len(preorder)]),
	}
}

func find(preorder, inorder []int) int {
	for i := 0; i < len(inorder); i++ {
		if preorder[0] == inorder[i] {
			return i
		}
	}
	return -1
}

func find1(preorder, postorder []int) int {
	for i := 0; i < len(postorder); i++ {
		if preorder[1] == postorder[i] {
			return i
		}
	}
	return -1
}

func levelOrder(root *TreeNode) [][]int {
	res := [][]int{}

	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if len(res) <= depth {
			res = append(res, []int{})
		}
		res[depth] = append(res[depth], node.Val)
		dfs(node.Left, depth+1)
		dfs(node.Right, depth+1)
	}

	dfs(root, 0)
	return res
}

func main() {
	c := buildTree(preorder, inorder)
	fmt.Println(c)
	fmt.Println(find(preorder, inorder))
	fmt.Println(levelOrder(c))
	fmt.Println(len(inorder[0:2]))
	d := constructFromPrePost(preorder, postorder)
	fmt.Println(levelOrder(d))
}
